#encoding=utf-8

'''
[54,26,93,17,77,31,44,55,20]  升序
基准数：54  比54小的放左边，大的放右边
low=1
high=n-1
'''

def quick_sort(alist, start, end):
    #递归退出条件
    if start>=end:
        return
    mid=alist[start]
    low=start
    high=end

    while low<high:

        #从右向左 alist[high]>mid 则high=1
        while low<high and alist[high]>=mid:
            high-=1
        #将high索引对应的元素赋值给low
        alist[low]=alist[high]

        #从左往右 alist[low]<mid 则low+=1
        while low<high and alist[low]<mid:
            low+=1
        alist[high]=alist[low]

    #将基准数放置到对应的位置
    alist[low]=mid

    #比基准数小的即左边的数据 要重复调用quick_sort()
    quick_sort(alist, start,low-1)
    # 比基准数大的即右边的数据 要重复调用quick_sort()
    quick_sort(alist, low+1, end)

if __name__ == "__main__":
    alist=[54,26,93,17,77,31,44,55,20]
    print("原列表：",alist)
    quick_sort(alist, 0, len(alist)-1)
    print("快速排序后的列表：",alist)

#时间复杂度：最优O(nlogn);最坏： O(n^2) 不稳定